package j2024.j202407;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Scanner;
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class j0723 {
    /**
     * 18. 四数之和
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int sz = nums.length;
        for (int i = 0; i < sz; ) {
            //固定a
            for (int j = i+1; j < sz; ) {
                int left = j+1,right = sz-1;
                long t = (long) target-nums[i]-nums[j];
                while(left<right){
                    if(nums[left] + nums[right] == t){
                        List<Integer> r = new ArrayList<>();
                        r.add(nums[i]);
                        r.add(nums[j]);
                        r.add(nums[left]);
                        r.add(nums[right]);
                        ret.add(r);
                        left++;
                        right--;
                        while(left<right && nums[left]==nums[left-1]){
                            left++;
                        }
                        while(left<right && nums[right]==nums[right+1]){
                            right--;
                        }
                    } else if (nums[left] + nums[right] > t) {
                        right--;
                    }else {
                        left++;
                    }
                }
                j++;
                while(j<sz && nums[j]==nums[j-1]){
                    j++;
                }
            }
            i++;
            while(i<sz && nums[i]==nums[i-1]){
                i++;
            }
        }
        return ret;
    }


    /**
     * 206. 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newhead = reverseList(head.next);
        System.out.println(newhead.val);
        head.next.next = head;
        head.next = null;
        return newhead;
    }


    /**
     * 21. 合并两个有序链表
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1.val<list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }





    /**
     * 面试题 08.06汉诺塔问题
     * @param A
     * @param B
     * @param C
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        //A借助B把所有盘子放到C上面
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n){
        if(n==1){
            C.add(A.get(A.size()-1));
            A.remove(A.size()-1);
            return;
        }
        //1.n-1个盘子从A借助C放到B上面
        dfs(A,C,B,n-1);
        //2.把A最下面的盘子放到C上
        C.add(A.get(A.size()-1));
        A.remove(A.size()-1);
        //3.把n-1个盘子从B借助A放到C上
        dfs(B,A,C,n-1);

    }


    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(),n = in.nextInt();
        String[] str = new String[m+1];
        for (int i = 1; i <= m; i++) {
            str[i] = in.next();
        }
        char[][] s = new char[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] = str[i].charAt(i);
            }
        }
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int t = 0;
                if(s[i][j]=='l'){
                    t = 4;
                }else if (s[i][j] == 'o'){
                    t = 3;
                } else if (s[i][j] == 'v') {
                    t = 2;
                }else if (s[i][j] == 'e'){
                    t = 1;
                }
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+t;
            }
        }
        System.out.println(dp[m][n]);
    }
    public static int MLS (int[] arr) {
        // write code here
        if(arr.length==0||arr==null){
            return 0;
        }
        int count = 1;
        int tmp = 1;
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]==arr[i-1]){
                continue;
            }else if(arr[i-1] == arr[i]-1){
                tmp++;
            }else {
                tmp = 1;
            }
            count = Math.max(count,tmp);
        }
        return count;
    }
    public static void main3(String[] args) {
        int[] a = {1,4,33,12,13,14,15,16};
        System.out.println(MLS(a));
    }
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = a % b;
        long d = (long) a*(long) b;
        while(c!=0){
            a = b;
            b = c;
            c = a%b;
        }

        System.out.println(d/b);
    }
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int m = a*b;
        int n = Math.max(a,b);
        for (int i = n; i <= m; i++) {
            if(i%a==0 && i%b==0){
                System.out.println(i);
                break;
            }
        }
    }
}
